1. Technical Field
The present invention relates in general to data communications between components of a data processing system. More particularly, the invention relates to a queue management facility partially implemented in hardware resulting in a relatively inexpensive queuing mechanism with increased performance over totally software managed queue structures.
2. Background of the Invention
In data processing systems, a queue is commonly used to store a backlog of tasks that have been assigned to a unit of the system by other system units. A queue is implemented as memory, or a portion of memory, in which items of information--queue entries--are stored in the order in which they are received from the task requesting units, and from which they are retrieved in the same order by the task performing unit. Some queues have been managed by hardware logic circuitry and other queues have been managed by program or microprogrammed routines.
Two implementations of queues are common. One is a first-in/first-out (FIFO) memory, having the property that an item of information loaded into its input register, which is located at the tail end of the queue, automatically propagates through empty memory locations towards output registers located at the head end of the queue, and is stored in the first empty location closest to the output register. Retrieval of an item of information from the output register causes all items remaining in the FIFO to shift one location closer to the output register. The other common implementation of a queue is a circular buffer having a read and write pointer associated therewith. The read pointer indicates the location at the head end of the queue from which the next item of information is to be retrieved and the write pointer indicates the location at the tail end of the queue into which the next item of information is to be stored. Retrieval of an item causes the read pointer to point to the next consecutive location that holds information, while storage of an item of information causes the write pointer to point to the next consecutive free location, available for information storage.
In conventional data processing systems, task requestors and the task performer are allowed to communicate to the queue only. That is, a task requestor may not transfer a task to the task performer directly, by bypassing the queue, even when the task performer is idle or waiting receipt of a task. The process of storing a task in a queue, then either propagating it through the FIFO queue or changing pointers on a circular buffer queue, and finally retrieving a task from the queue, takes time and hence the system is slowed down by these procedures and performance is adversely affected. Conventional queue administration systems are often not efficient in transferring information between devices that store information in the queue and devices that retrieve information from the queue.
Queues implemented in hardware are expensive and require a lot of integrated circuitry. Hardware managed queue structures require memory address buses, data bus, and multiplexing logic. There is a great deal of complexity in the memory timing and control logic necessary to access the queue memory. Because of these timing delays, there is a great latency in queue data transfers because of the indivisible, uninterruptible memory operations needed.
In a software managed queue structure there is a need to update the software and verify the queue write and queue read pointers. There is a need to determine queue overflow, underflow and other error conditions. The software must be used to set/clear the queue interrupts. Much internal central processing time and external memory sources are needed to hold the necessary pointer array. The programming code storage requirements of a software managed queue is very large.
What is needed is a relatively inexpensive queuing mechanism with increased performance to handle high speed data communications within a data processing system.